Розглянуто метод побудови точних і наближених рішень задачі (0,1)-рюкзак на основі рангового підходу та оптимізації за напрямком у дискретному просторі станів. Показано, що цей метод дозволяє будувати точні рішення задачі (0,1)-рюкзак протягом поліноміального часу з довірчою вірогідністю 0,95.

Розглянуто метод побудови точних і наближених розв'язків задачі про мінімальне покриття на основі рангового підходу в дискретному просторі станів. Показано, що даний метод у ряді випадків дозволяє отримати точні розв'язки задачі про мінімальне покриття протягом поліноміального часу.

Запропоновано алгоритми, які дозволяють підвищити точність розв'язання задачі 0,1-рюкзак, і паралельні обчислювальні структури для їхньої реалізації в масштабі реального часу.

Описаны методы решения задач дискретной оптимизации, а также произвольных задач булевого программирования и оптимизации на графах. Рассмотрены особенности применения рангового подхода к решению данных задач и теории графов, являющихся формальными моделями широкого класса задач управления в сложных системах управления и сетях. Приведены универсальные алгоритмы их решения, а также модели многопроцессорных вычислительных систем.

Рассмотрены проблемы исследования новых методов применения теории алгоритмов и теории графов в задачах распределения в современных распределенных информационно-вычислительных системах нового поколения - GRID-системах. Раскрыты вопросы оптимального планирования ресурсов на основе рангового подхода к решению задач булевого программирования, оптимизации поиска информационных ресурсов, в том числе на основе методов интеллектуального анализа данных, реализован метод решения задачи о наименьшем покрытии.

Запропоновано алгоритми визначення мінімальних вершинних покриттів та максимальних незалежних множин у довільних графах для випадків зважених та незважених вершин, які мають поліноміальну часову складність.

Запропоновано алгоритм поліноміальной складності для розв'язування задачі три-виконуваність.

Запропоновано стратегії відсікання безперспективних варіантів розв'язування задач лінійного програмування з булевими змінними на основі рангового підходу за рахунок введення песимістичного гарантованого прогнозу. Показано, що використання таких стратегій дозволяє істотно підвищити точність наближених алгоритмів розв'язування та зменшити часову складність точних алгоритмів розв'язування задач лінійного программування з булевими змінними.

Предложен метод на основе идей рангового подхода, позволяющий получить приближенные алгоритмы для решения любых задач линейного и нелинейного булевого программирования с полиномиальной временной сложностью и погрешностью, не превышающей 5 - 10 % при числе ограничений больше 50. При этом с увеличением числа ограничений погрешность асимптотически уменьшается.

Ключ. слова: полиномиальный алгоритм, наименьшее вершинное покрытие, произвольный граф
Індекс рубрикатора НБУВ: В173.112

Рубрики:

Дискретне програмування

Шифр НБУВ: Ж70474 Пошук видання у каталогах НБУВ 

Оценены методы управления запросами и показано, что эффективным является метод групповой выборки, при реализации которого из очереди запросов обслуживается несколько запросов одновременно, и выбираются запросы, так чтобы сумма их приоритетов была максимальной. Установлено, что все множество запросов в общем виде можно описать характеристической нелинейной булевой функцией и при этом наиболее перспективным подходом к управлению обработки запросов является сведение этой задачи к задачам линейного и нелинейного булевого программирования, однако при этом требуется иметь эффективные, с точки зрения временной сложности, алгоритмы их решения.

На основе идей рангового подхода предложен метод, позволяющий решать задачи линейного булевого и нелинейного булевого программирования с единых позиций, что достигнуто благодаря использованию представления пространства решений в виде симметричного графа и разработки процедуры отсечения неперспективных вариантов с использованием принципа оптимизации по направлению. Показано, что данный подход позволяет получить эффективные приближенные алгоритмы решения данной задачи, имеющие полиномиальную временную сложность. При этом погрешность решений в случае равномерного закона распределения коэффициентов в функционале и ограничениях при числе ограничений больше 60 не превышает 2 - 6 %. Показано, что с увеличением размерности решаемой задачи и числа ограничений в ней погрешность в среднем у предложенных алгоритмов асимптотически уменьшается.

Предложена универсальная процедура решения произвольных задач дискретной оптимизации, которая может быть эффективно распараллелена для решения на основании циклических параллельных вычислительных структур. Решение задач основано на представлении пространства возможных решений задач дискретной оптимизации и теории графов в виде стянутого древа всех путей, что позволяет сводить решение рассматриваемых задач к определению экстремальных путей в стянутом дереве путей, формирование которых на ярусе дерева может осуществляться одновременно, что и позволяет организовать эффективное распараллеливание вычислительного процесса.

Індекс рубрикатора НБУВ: В192.19

Рубрики:

Чисельні методи оптимізації та моделювання

Шифр НБУВ: Ж73223 Пошук видання у каталогах НБУВ 

Індекс рубрикатора НБУВ: В173.111

Рубрики:

Лінійне програмування

Шифр НБУВ: Ж14163 Пошук видання у каталогах НБУВ 

Предложены универсальные процедуры решения широкого класса задач дискретной оптимизации, которые могут эффективно распараллеливаться на основании циклических параллельных вычислительных структур. Решение задач базируется на определении пространства возможных решений задач дискретной оптимизации и теории графов в виде стянутого дерева всех путей. Формирование экстремальных путей на ярусе дерева может осуществляться одновременно, что позволяет организовать эффективное распараллеливание вычислительного процесса. Проанализированы возможности использования предложенных обобщенных процедур для построения интеллектуальных вычислительных систем.

Предложена новая постановка задачи для формализации выбора оптимальной проектной структуры организации, основой которой являются современные методологии разработки сложных программных систем, сводящаяся к нелинейным булевым уравнениям. Разработана процедура, использующая ранговый подход к решению задач комбинаторной оптимизации, имеющая полиномиальную временную сложность. Приведены результаты статистического моделирования.

Індекс рубрикатора НБУВ: В173.112.1

Рубрики:

Комбінаторне програмування

Шифр НБУВ: Ж14163 Пошук видання у каталогах НБУВ 

Предложен субэкспоненциальный алгоритм решения SAT-задачи.

Предложена модель и подход к планированию вычислительных ресурсов в двухуровневой Грид-системе. Разработана динамическая процедура планирования распределения ресурсов в гетерогенной среде на основе решения задачи о наименьшем покрытии, а также программный продукт, реализующий имитационную дискретно-событийную модель планирования. Приведены вычислительные эксперименты на основе программной реализации модели, обосновывающие эффективность предложенной модели планирования распределения ресурсов в гетерогенных системах в выбранных метриках производительности работы системы. Показано, что предложенная процедура планирования позволяет максимизировать загрузку гетерогенных ресурсов системы, уменьшить время выполнения всей очереди заданий в Грид-системе по сравнению с распространенным методом FCFS. Рассмотрена реализация предложенного метода в планировщике MAUI.